package com.example.interview.algorithm;

/**
 * 重建二叉树
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月28日 上午11:05:14
 * 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}，重建出下图所示的二叉树并输出它的头结点。
  */
public class Test07Tree {
  
    // 输入的两个序列不匹配
	private static void test7() {
		 int[] preorder = {1, 2, 4, 5, 3, 6, 7};       
		 int[] inorder = {4, 2, 8, 1, 6, 3, 7};        
		 BinaryTreeNode root = construct(preorder, inorder);        
		 printTree(root);

 
 	}
 
	//输入空指针
	private static void test6() { 
        construct(null, null);
		
	}

	// 完全二叉树
    //              1
    //           /     \
    //          2       3
    //         / \     / \
    //        4   5   6   7
	private static void test5() {
		int[] preorder = {1, 2, 4, 5, 3, 6, 7};        
		int[] inorder = {4, 2, 5, 1, 6, 3, 7};        
		BinaryTreeNode root = construct(preorder, inorder);        
		printTree(root);

 	}
	  // 树中只有一个结点
	private static void test4() {
		int[] preorder = {1};
        int[] inorder = {1};
        BinaryTreeNode root = construct(preorder, inorder);
        printTree(root); 
	}
	// 所有结点都没有左子结点    
	//            1    
	//             \    
	//              2    
	//               \    
	//                3    
	//                 \    
	//                  4    
	//                   \    
	//                    5 
 	private static void test3() {
 		int[] preorder = {1, 2, 3, 4, 5};        
 		int[] inorder = {1, 2, 3, 4, 5};        
 		BinaryTreeNode root = construct(preorder, inorder);        
 		printTree(root);


 	}
	
	// 所有结点都没有右子结点   
	//            1    
	//           /    
	//          2    
	//         /    
	//        3    
	//       /    
	//      4    
	//     /    
	//    5    

 
 	private static void test2() {
		int[] preOrder= {1,2,3,4,5};
		int[] inOrder= {5,4,3,2,1};
		BinaryTreeNode root=construct(preOrder, inOrder);
		printTree(root);
		
	}
	// 普通二叉树    
	//  			1    
	//           /     \   
	//          2       3    
	//         /       / \    
	//        4       5   6    
	//         \         /    
	//          7       8

  	private static void test1() {
		 int[] preOrder= {1,2,4,7,3,5,6,8};
		 int[] inOrder= {4,7,2,1,5,3,8,6};
		 BinaryTreeNode root=construct(preOrder,inOrder);
		 printTree(root);
	}
	
  	/**
  	 * 打印二叉树
  	 * @param root
  	 */
	private static void printTree(BinaryTreeNode root) {
		if (root!=null) {
			printTree(root.left);
			System.out.println(root.value+" ");
			printTree(root.right);
		}
	}

	/**
	 * 
	 * @param preOrder 前序遍历
	 * @param inOrder  中序遍历
	 * @return
	 */
	private static BinaryTreeNode construct(int[] preOrder, int[] inOrder) {
		//输入合法性判断，两个数组都不能为空，并且都有数据并且数目相等
		if (preOrder==null||inOrder==null||preOrder.length!=inOrder.length||inOrder.length==0) {
			return null;
		}
		return construct(preOrder, 0,preOrder.length-1,inOrder,0,inOrder.length-1);
	}
	
	/**
	 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
	 * @param preOrder 前序遍历
	 * @param ps       前序遍历的开始位置
	 * @param pe	         前序遍历的结束位置
	 * @param inOrder  中序遍历
	 * @param is       中兴遍历的开始位置
	 * @param ie       中序遍历的结束位置
	 * @return
	 */
	private static BinaryTreeNode construct(int[] preOrder, int ps, int pe, int[] inOrder, int is, int ie) {
		if (ps > pe) {
			return null; //开始位置大于结束位置说明已经没有需要处理的元素了
		}
		//取前序遍历的第一个数字就是当前的根节点
		int value=preOrder[ps];
		int index=is;
		//在中序遍历的数组中找跟节点的位置，索引
		while(index <=ie && inOrder[index]!=value) {
			index++;
		}
		//如果在整个中序遍历中没有找到，说明输入的参数是不合法的，抛出异常
		if (index>ie) {
			throw new RuntimeException("Invalid input");
		}
		//创建当前的根节点，并且为节点赋值
		BinaryTreeNode node=new BinaryTreeNode();
		node.value=value;
		
		//递归构建当前根节点的左子树，左子树的元素个数 index-is+1
		//左子数对应的前序遍历的位置在 [ps+1,ps+index-is]
		//左子树对应的中序遍历的位置[is,index-1]
		//前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}
		node.left=construct(preOrder, ps+1, ps+index-is, inOrder, is, index-1);
		
		//递归构建当前根节点的右子树，右子树的元素个数：ie-index
		//右子树对应的前序遍历的位置在[ps+index-is+1]
		//右子树对应的中序遍历的位置 [index+1,ie]
		//前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}
		node.right=construct(preOrder, ps+index-is+1, pe, inOrder, index+1, ie);
		
		//返回创建的根节点
		return node;
	} 

	/**
	 * 二叉树结点类
	 * @Description: TODO
	 * @author gaobing
	 * @date 2018年9月28日 上午11:14:19
	 *
	 */
	public static class BinaryTreeNode{
		int value;
		BinaryTreeNode left;
		BinaryTreeNode right;
	}

	public static void main(String[] args) {
		test1();
		System.out.println();
		test2();
		System.out.println();
		test3();
		System.out.println();
		test4();
		System.out.println();
		test5();        
		System.out.println();        
		test6();        
		System.out.println();        
		test7();

 
 	}

	
}
